package com.jxm.graph;

import com.jxm.linear.Stack;

/**
 * @Author: jxm
 * @Description: 顶点排序API设计
 * @Date: 2022/8/3 11:36
 * @Version: 1.0
 */
public class DepthFirstOrder {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //使用栈，存储顶点序列
    private Stack<Integer> reversePost;

    //创建一个顶点排序对象，生成顶点线性序列
    public DepthFirstOrder(Digraph G){
        this.marked = new boolean[G.V()];
        this.reversePost = new Stack<>();
        //遍历图中每个顶点，让每个顶点作为入口，完成一次深度优先搜索
        for (int v = 0; v < G.V(); v++) {
            if(!marked[v]){
                dfs(G,v);
            }
        }
    }

    /**
     * 基于深度优先搜索，生成顶点线性序列
     * @param G
     * @param v
     */
    private void dfs(Digraph G,int v){
        //标记当前v已经被搜索
        marked[v] = true;
        //通过循环深度搜索顶点v
        for (Integer w:G.adj(v)){
            //如果顶点w没有被搜索，则递归调用dfs进行搜索
            if(!marked[w]){
                dfs(G,w);
            }
        }
        //让顶点v进栈
        reversePost.push(v);
    }

    /**
     * 获取顶点线性序列
     * @return
     */
    public Stack<Integer> reversePost(){
        return reversePost;
    }
}
